# 最大矩形.py: https://leetcode-cn.com/problems/maximal-rectangle/submissions/

class Solution:
    def maximalRectangle(self, matrix: list) -> int:
        """
            这道题抽象一下，和84号题柱状图中最大的矩阵是一模一样！
            横着看， 想象坐标系的 x， y轴， 矩阵的每一列都是坐标的x轴， 从右往左方向 是y轴！
            这个时候，如果只看连续的1， 那么又可以看成是柱状图！ 然后求其中最大的 矩阵（全1的矩阵）
            所以做这道题一定要有 84 号题的基础。 加入矩阵有 n 列， 这题就相当于有 n 个 柱状图，去求其中最大的那个矩阵！！！ 完美解释！
        """

        # 1. 如果列表为空，返回0
        if not matrix: return 0

        # 2. 先对原来的二维矩阵进行标记代表当前柱子的高度, n行 m列的矩阵
        n = len(matrix)
        m = len(matrix[0])
        for i in range(n):
            for j in range(m):
                matrix[i][j] = int(matrix[i][j])
                if j > 0 and  matrix[i][j] > 0 and matrix[i][j - 1] > 0:
                    matrix[i][j] += matrix[i][j - 1]

        # 3. 求以每列为x 轴的柱状图对应的最大矩形面积,# 这里的代码就是 完完全全的84题的代码了！ 没有使用最优解，一个循环求left， right
        rst = 0
        for j in range(m):
            # 定义 求左边最近最小值和右边最近最小值的数组和栈, 默认值为 -1， n
            left = [-1] * n
            right = [n] * n
            stack = list()
            
            # 求左边
            for i in range(n-1, -1, -1):
                while stack and matrix[i][j] < matrix[stack[-1]][j]:
                    left[stack.pop()] = i
                stack.append(i)
            stack.clear()

            # 求右边
            for i in range(n):
                while stack and matrix[i][j] < matrix[stack[-1]][j]:
                    right[stack.pop()] = i
                stack.append(i)

            # 计算面积
            for i in range(n):
                width = right[i] - left[i] - 1
                high = matrix[i][j]
                area = width * high
                rst = max(area, rst)
        
        # # 打印矩阵
        # for i in range(n):
        #     print(matrix[i])

        return rst




